
/*
* 实现一个 统计 整数数据的出现次数
* key - 整形数据
* value - key 元素 的 出现次数
* */

public class HashTable {
    // 节点类 - 静态内部类
  static class Node{
      public int key;
      public int val;
      public Node next;
      public Node(int key,int val){
          this.val = val;
          this.key = key;
      }
  }

  public Node[] array;// 底层数组
  public int usedSize;// 元素个数
  public  static final double DEFAULT_LOAD_FACTOR = 0.75;// 负载因子
  public HashTable(){
      // 数组初始容量为 10
      this.array = new Node[10];
  }

/*
* 根据 key 获取 val 值
* */
  public int get(int key){
      // 1、 找到 key 所在的 位置。
      int index = key % this.array.length;
      // 2、遍历数组，寻找 key
      Node cur = this.array[index];
      while(cur!=null){
          if(cur.key == key){
              return cur.val;
          }
          cur = cur.next;
      }
      // 返回-1,表示没有找到符号条件的节点
      return -1;
  }

  /*
  * 将 key ，value 值 存入
  * 此时的代码是有缺陷的，key 不能为负数
  * */
  public void put(int key,int val){
      // 1、 找到 key 所在的 位置。
      int index = key % this.array.length;
      // 2、遍历这个下标的链表
      Node cur = array[index];// 获取头节点地址
      while(cur!=null){
//  判断是否有相同的key，有，则更新value值
          if(cur.key == key){
              cur.val = val;
              return;
          }
          cur = cur.next;
      }
      // 没有相同的key，就直接头插节点
      Node node = new Node(key,val);
      node.next = array[index];
      array[index] = node;
      this.usedSize++;
      // 检查当前的负载因子
      if(loadFactor() > DEFAULT_LOAD_FACTOR){
          resize();// 扩容
      }

  }
  private double loadFactor(){
      return 1.0 * this.usedSize / this.array.length ;//乘以1.0为了结果是小数。
  }
  private void resize(){
      Node[] newArray = new Node[this.array.length*2];
      for (int i = 0; i < this.array.length; i++) {
          Node cur = this.array[i];
          while(cur!=null){
              // 获取 在 新数组中的 存储位置。
              int index = cur.key % newArray.length;
              // 头插到新数组中
              Node curNext = cur.next;// 记录下一个节点的位置
              cur.next = newArray[index];
              newArray[index] =  cur;
              cur = curNext;// 接着下一个节点。
          }
          // while循环执行完之后，for循环i++，继续下一个下标的哈希
      }
      // 最后更新 array 的 引用大的指向
      this.array = newArray;
  }

    public static void main(String[] args) {
        HashTable hashTable = new HashTable();
        hashTable.put(1,1);
        hashTable.put(3,3);
        hashTable.put(12,12);
        hashTable.put(2,2);// 冲突元素
        hashTable.put(11,11);// 冲突元素
        hashTable.put(15,15);
        hashTable.put(4,4);
        hashTable.put(5,5);// 冲突元素
        // 5个元素，此时的负载因子为0.5
        System.out.println(hashTable.get(11));

    }
}
